|
課程名稱 |
離散最佳化
DISCRETE OPTIMIZATION |
|
開課學期 |
99-1 |
|
授課對象 |
電機資訊學院 電機工程學研究所 |
|
授課教師 |
張時中 |
|
課號 |
EE5077 |
|
課程識別碼 |
921 U3410 |
|
班次 |
|
|
學分 |
3 |
|
全/半年 |
半年 |
|
必/選修 |
選修 |
|
上課時間 |
星期二5(12:20~13:10)星期四7,8(14:20~16:20) |
|
上課地點 |
電二225電二225 |
|
備註 |
總人數上限：40人 |
|
Ceiba 課程網頁 |
http://ceiba.ntu.edu.tw/991_dis_opt |
|
課程簡介影片 |
|
|
核心能力關聯 |
本課程尚未建立核心能力關連 |
|
課程大綱
|
|
為確保您我的權利,請尊重智慧財產權及不得非法影印
|
|
課程概述 |
Tentative Outline
1.Course Overview, Algorithms and Complexity and Basics of Optimization.
2.Linear Programming (LP): Problems, Properties and Simplex Algorithms
3.Duality Theorem and Sensitivity
4.Interior Point Methods for LP
5.Network Optimization: Representation, Shortest Path Algorithm and Minimum Spanning Tree Algorithm
6.Maximum Flow and Minimum Cost Flow Algorithms
7.Integer Programming Problems: Traveling Salesman, Knapsack, …
8.Barnch-and-Bound and Cutting Plan Methods
9.Integer Linear Programming and CPLEX
10.Mid-term Exam
11.Term Project Topic Identification and Team Forming
12.Simulated Annealing & Tabu Search
13.Genetic Algorithms & Artificial Neural Networks for Optimization
14.Constraint Optimization
15.Term Project Presentations
|
|
課程目標 |
- To introduce to students the theory, models, analysis, approximations and algorithms of optimization over discrete variables
- To guide students to apply the theory to and design methods for solving electrical engineering and computer science problems. |
|
課程要求 |
Grading
Homework 20% Mid-term Exam 40% Term Project 40%
Participation 5% |
|
預期每週課後學習時數 |
|
|
Office Hours |
另約時間 |
|
指定閱讀 |
Textbook
C. H. Papadimitriou, K. Steiglitz, Combinatorial Optimization:Algorithms and Complexity, Prentice Hall, 1982. |
|
參考書目 |
References
1. E. Aarts, J. K. Lenstra, eds., Local Search in Combinatorial Optimization, Wiley, 1997.
1.http://en.wikipedia.org/wiki/Combinatorial_optimization
2.J. of Combinatorial Opt. http://www.kluweronline.com/issn/1382-6905
3.Discrete Optimization http://www.elsevier.com/locate/disopt
4.No free lunch in search and optimization
5.Discrete Optimization methods
www.cs.sunysb.edu/~algorith/implement/syslo/implement.shtml
|
|
評量方式
(僅供參考) |
|
|
週次 |
日期 |
單元主題 |
|
第1週 |
9/14,9/16 |
Course Overview, Algorithms and Complexity and Basics of Optimization. |
|
第2週 |
9/21,9/23 |
Algorithms and Complexity;Linear Programming: Problems, Properties, and Simplex Algorithm in Matrix Form |
|
第3週 |
9/28,9/30 |
Linear Programming: Simplex Algorithms, Duality and Sensitivity |
|
第4週 |
10/05,10/07 |
Complementary slackness, sensitivity, Karmakar's interior point algorithm |
|
第5週 |
10/12,10/14 |
Introduction to Network Optimization Problem, Network representation |
|
第6週 |
10/19,10/21 |
Minimum Spanning Tree Problems
–Problem description and greedy algorithm
–Mathematical Formulation
–Optimality proof
Maximum Flow Problem
–Formulation
–Minimum cut, max flow and dualityMaximum Flow Problem
Total Unimodularity
–Minimum cut, max flow and duality |
|
第7週 |
10/26,10/28 |
minimum cost networkflow problem - negative cycle canceling; MCNFP and other network problem conversion. |
|
第8週 |
11/02,11/04 |
matching problems and algorithms; Introduction to branch and bound; |
|
第9週 |
11/09,11/11 |
Traveling Salesman Problem - Branch and Bound(B&B), Cutting Plane Method(Gomory’s Cut); Introduction to scheduling problems; |
|
第10週 |
11/16,11/18 |
Scheduling problems and algorithms: single machine, parallel machine, flow shop scheduling |
|
第11週 |
11/23,11/25 |
Introduction of iLog optimization tool suites CPLEX; 11/25 midterm exam |
|
第12週 |
11/30,12/02 |
Parallel Machine Scheduling; Flow Shop Scheduling and Rescheduling
|
|
第13週 |
12/07,12/09 |
Local Search;Meta-Heuristic Search; Specific Search Strategies;Simulated Annealing; |
|
第14週 |
12/14,12/16 |
Simulated Annealing(Cont.); Stochastic Machines; Convergence Analysis; Genetic Algorithm; |
|
第15週 |
12/21,12/23 |
Genetic Algorithm; Monte Carlo Simulation -based Optimization |
|
第16週 |
12/28,12/30 |
Stochastic optimization problem
Stochastic simulation (Monte Carlo)
Efficient techniques:
Ordinal Optimization (OO)
Optimal Computing Budget Allocation (OCBA)
Application to scheduling semiconductor fabs |
|
第17週 |
1/04,1/06 |
Introduction to constraint programming: modeling, constraint propagation, search, best solution |
|
第18週 |
01/11, 13/2011 |
no class; term project preparation; |
|
第19週 |
01/19, 20/2011 |
Term project presentations |
|